def mySqrt(x):
    left, right = 0, x
    mid = 1
    while left <= right:
        mid = left + (right - left) // 2
        mid_square = mid ** 2
        if mid_square == x or (mid_square < x and (mid + 1) ** 2 > x):
            return mid
        if mid_square > x:
            right = mid - 1
        else:
            left = mid + 1
    return mid


print(4, mySqrt(4))  # 4 2
print(2, mySqrt(2))  # 2 1
print(8, mySqrt(8))  # 8 2
print(9, mySqrt(9))  # 9 3
print(11, mySqrt(11))  # 11 3
print(1, mySqrt(1))  # 1 1
